Many prior vehicle route planning systems are known in which data concerning fixed roadways in a predetermined geographical area are stored in a memory device and the route planning system utilizes such data in determining an optimum route to a desired destination via the fixed roadways. Most prior automobile/vehicle route planning systems for planning travel along fixed roadways utilize some form of such prior systems. In such prior systems the desired route is achieved by accessing the data defining all of the possible roadways for travel and then selecting, according some predetermined criteria, which fixed roadways should be utilized to define an optimum path to the desired destination.
In some of the above noted prior route planning systems, the roadway data is stored hierarchically in several different layers of road data with, typically, one layer representing a detailed road layer in which all roadways are designated and another layer representing a higher layer containing just vehicle roadways having certain travel characteristics rather than all roadways. Thus a detailed roadway layer having every road and street of every type is provided, and then, for example, a higher layer of roads having information about just major roads and limited access expressways may be provided. Of course this can be extended such that an even higher layer of roadways can be stored having, for example, just limited access expressway roads. In such prior systems, typically route planning occurs by having origin and destination locations located on the most detailed layer. Then, a route is provided to an intersection of roadways that are defined on the next higher roadway layer. Then, route planning is implemented on the higher roadway layer. In this manner, more efficient route planning is achieved since the majority of the route planning will occur at the higher road layer which therefore will ignore data and potential road choices relating to roadways not designated in this higher layer. Several such prior multiple layer systems are known and have been described in various articles.
In previously known multiple layer road memory devices, and route planning systems which utilize such devices, each roadway in each layer is defined by road segments which make-up each roadway, and each road segment extends between intersections of that roadway with other roadways in the same layer. Route planing occurs by determining, at each intersection, what other road segments are connected to that intersection. Then, one of the these road segments is selected for use in the desired route. The route segment selection typically occurs in accordance with some predetermined criteria, and several systems are known which utilize various criteria for accomplishing this. In some systems, a route is determined by simultaneously searching from both the origin and the destination for a desired route. The search ends when a common road segment is found by this simultaneous double searching. An example of this type of searching is commonly known as the double ended A-star algorithm.
In known prior route planning systems which utilize multiple layer road data storage, the layers differ only in that some road segments found in the lower layer are not carried forward into the higher layer since the roadways defined by those segments are not to be provided or designated in the higher layer. For roadways which are defined in both the higher and lower layers, the road segments which define the roadway in the lower layer are reproduced substantially exactly in the higher layer. Thus some road segment data in the first layer is just duplicated in the second layer and no reformatting of this data is needed. However, one result of this is that a relatively large amount of memory is required for the higher layer because all of the small road segments for a roadway contained in the lower layer are carried forward into the higher layer if the roadway is also contained in the higher layer. A more significant disadvantage of the prior systems is that route planning still is relatively time consuming because decisions are made at the end of each and every road segment as to whether or not there are any additional road segments connected to these road segments and which of these additional road segments are to be selected. The route planning process generally always implements such steps even though there is only one road segment that is connected to the end of another road segment in the second layer. While the prior systems have an advantage in that the roadway data in the second layer is just a direct subset of the roadway data in the first layer, this is offset by the fact that the second layer requires a substantial amount of memory, and also by the fact that the time for route planning still is relatively lengthy, especially when route planning takes place over a substantial distance and therefore involves several hundred or several thousand individual road segments.